package com.hy;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:二叉树的最小深度
 * 给定一个二叉树，找出其最小深度。
 *
 * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 *
 * 说明：叶子节点是指没有子节点的节点。
 * author: Mr.Du
 * Date: 2023/9/12
 * Time: 9:39
 */
public class MinDepth {

    /**
     * 注意最小深度的定义
     * @param root
     * @return
     */
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        int m1 = minDepth(root.left) + 1;
        int m2 = minDepth(root.right) + 1;
        if(root.left == null) return m2;
        if(root.right == null) return m1;
        return Math.min(m1,m2);
    }

    public int minDepth1(TreeNode root){
         if (root == null) return 0;
         int left = minDepth1(root.left);
         int right = minDepth1(root.right);
         // 因为是根节点到叶子节点，所以说，左/右子树为空，那么就1 + 右/左子树的高度
         if (left == 0 || right == 0) return Math.max(left, right) + 1;
         return Math.min(left, right) + 1;
    }

    public int minDepth2(TreeNode root){
        if(root == null) return 0;
        int depth = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int sz = queue.size();
            depth++;
            for(int i = 0;i < sz;i++){
                root = queue.poll();
                if(root.left != null) queue.offer(root.left);
                if(root.right != null) queue.offer(root.right);
                if(root.left == null && root.right == null) return depth;
            }
        }
        return depth;
    }
}
